package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //图像渲染
        class Solution {
            int[] dx = {0, 0, 1, -1};  // 四个方向：右、左、下、上
            int[] dy = {1, -1, 0, 0};
            int m, n;      // 图像尺寸
            int originalColor;  // 原始颜色

            public int[][] floodFill(int[][] image, int sr, int sc, int color) {
                originalColor = image[sr][sc];
                // 如果新颜色与原颜色相同，直接返回避免无限递归
                if (originalColor == color) return image;

                m = image.length;
                n = image[0].length;

                dfs(image, sr, sc, color);
                return image;
            }

            private void dfs(int[][] image, int row, int col, int newColor) {
                // 将当前像素改为新颜色
                image[row][col] = newColor;

                // 遍历四个方向
                for (int i = 0; i < 4; i++) {
                    int newRow = row + dx[i];
                    int newCol = col + dy[i];

                    // 边界检查 + 颜色检查
                    if (newRow >= 0 && newRow < m &&
                            newCol >= 0 && newCol < n &&
                            image[newRow][newCol] == originalColor) {
                        dfs(image, newRow, newCol, newColor);
                    }
                }
            }
        }

        //岛屿数量
        class Solution2 {
            int[] dx = {0, 0, 1, -1};  // 四个方向：右、左、下、上
            int[] dy = {1, -1, 0, 0};
            int m, n;
            boolean[][] visited;

            public int numIslands(char[][] grid) {
                if (grid == null || grid.length == 0) return 0;

                m = grid.length;
                n = grid[0].length;
                visited = new boolean[m][n];
                int islandCount = 0;

                // 遍历整个网格
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        // 发现未访问的陆地，开始新的岛屿探索
                        if (grid[i][j] == '1' && !visited[i][j]) {
                            dfs(grid, i, j);
                            islandCount++;  // 完成一个岛屿的探索，计数加1
                        }
                    }
                }

                return islandCount;
            }

            private void dfs(char[][] grid, int row, int col) {
                // 标记当前位置为已访问
                visited[row][col] = true;

                // 探索四个方向
                for (int i = 0; i < 4; i++) {
                    int newRow = row + dx[i];
                    int newCol = col + dy[i];

                    // 边界检查 + 访问检查 + 陆地检查
                    if (newRow >= 0 && newRow < m &&
                            newCol >= 0 && newCol < n &&
                            !visited[newRow][newCol] &&
                            grid[newRow][newCol] == '1') {
                        dfs(grid, newRow, newCol);
                    }
                }
            }
        }
    }
}